Miller-Rabin test

INPUT: Số tự nhiên lẻ n.

OUTPUT: NguyenTo: TRUE/FALSE

1. Phân tích n − 1 = 2 s ⋅ m {\displaystyle n-1=2^{s}\cdot m} trong đó s ≥ {\displaystyle \geq } 1 và m là số tự nhiên lẻ
2. Chọn ngẫu nhiên số tự nhiên a ∈ { 2 , … ,   n − 1 } {\displaystyle a\in \{2,\dots ,\ n-1\}} .
3. Đặt b = a m ( mod n ) {\displaystyle b=a^{m}{\pmod {n}}}
4. Nếu b ≡ 1 ( mod n ) {\displaystyle b\equiv 1{\pmod {n}}} thì trả về TRUE. Kết thúc.
5. Cho k chạy từ 0 đến s:
   1. Nếu b ≡ − 1 ( mod n ) {\displaystyle b\equiv -1{\pmod {n}}} thì trả về TRUE. Kết thúc.
   2. Thay b := b 2 ( mod n ) {\displaystyle b^{2}{\pmod {n}}} .
6. Trả lời FALSE. Kết thúc.

Xác suất trả lời sai

Định lý: nếu n là hợp số dương lẻ thì trong các số a ∈ { 2 , … ,   n − 1 } {\displaystyle a\in \{2,\dots ,\ n-1\}} tồn tại không quá n − 1 4 {\displaystyle {\frac {n-1}{4}}} cơ sở a để n là số giả nguyên tố mạnh Fermat.

Gọi A là biến cố "Số n là hợp số", B là biến cố "Kiểm tra Miller-Rabin trả lời n là số nguyên tố". Khi đó xác suất sai của kiểm tra này là xác suất để số n là hợp số trong khi thuật toán cho câu trả lời TRUE, nghĩa là xác suất điều kiện P(A|B).

Theo định lý trên nếu n là hợp số thì khả năng kiểm tra này trả lời TRUE xảy ra với xác suất không vượt quá 1 4 {\displaystyle {\frac {1}{4}}} , nghĩa là P ( B | A ) ≤ 1 4 {\displaystyle P(B|A)\leq {\frac {1}{4}}} . Tuy nhiên để tính xác suất sai của kiểm tra Miller-Rabin cần tính xác suất diều kiện P(A|B). Dựa trên định lý về ước lượng số các số nguyên tố ta đưa ra ước lượng

P ( A ) ≈ 1 − 2 ln ⁡ n ≈ ln ⁡ n − 2 ln ⁡ n {\displaystyle P(A)\approx 1-{\frac {2}{\ln n}}\approx {\frac {\ln n-2}{\ln n}}}

Theo định lý Bayes trong lý thuyết xác suất ta có công thức để tính xác suất sai của kiểm tra Miller-Rabin là:

P ( A | B ) = P ( B | A ) ∗ P ( A ) P ( B ) {\displaystyle P(A|B)={\frac {P(B|A)*P(A)}{P(B)}}} = P ( B | A ) ∗ P ( A ) P ( B | A ) P ( A ) + P ( B | A ¯ ) ∗ P ( A ¯ ) {\displaystyle ={\frac {P(B|A)*P(A)}{P(B|A)P(A)+P(B|{\overline {A}})*P({\overline {A}})}}}

Trong công thức này P(A) đã biết ở trên, P ( B | A ) ≤ 1 4 {\displaystyle P(B|A)\leq {\frac {1}{4}}} , còn P ( B | A ¯ ) = 1 {\displaystyle P(B|{\overline {A}})=1} vì khi n là số nguyên tố thì chắc chắn mệnh đề Q(n, a) là đúng và P ( A ¯ ) = 1 − P ( A ) = 2 ln ⁡ n {\displaystyle P({\overline {A}})=1-P(A)={\frac {2}{\ln n}}} .Từ đó

P ( A | B ) = P ( B | A ) ∗ P ( A ) P ( B | A ) P ( A ) + P ( A ¯ ) {\displaystyle P(A|B)={\frac {P(B|A)*P(A)}{P(B|A)P(A)+P({\overline {A}})}}} P ( A | B ) ≈ P ( B | A ) ∗ ( ln ⁡ n − 2 ) P ( B | A ) ∗ ( ln ⁡ n − 2 ) + 2 {\displaystyle P(A|B)\approx {\frac {P(B|A)*(\ln n-2)}{P(B|A)*(\ln n-2)+2}}}

[1]

Kiểm tra Miller-Rabin lặp

Theo công thức tính xác suất sai trên đây, với n lớn (cỡ 130 chữ số thập phân), nếu thực hiện phép thử Miller-Rabin chỉ một lần, xác suất sai là khá lớn, tới trên 90%. Để giảm xác suất sai, ta lặp lại phép thử k lần với k số ngẫu nhiên a khác nhau, nếu n vượt qua 50 lần thử thì P ( B | A ) ≤ 1 4 k {\displaystyle P(B|A)\leq {\frac {1}{4^{k}}}} , khi thay vào công thức với 50 lần thử nếu cả 50 lần, phép thử đều "dương tính" thì xác suất sai giảm xuống chỉ còn là một số rất nhỏ không vượt quá 9 ⋅ 10 − 29 {\displaystyle 9\cdot 10^{-29}} .